package heap

import (
	"container/heap"
	"sort"
)

/*
	堆数据结构

排序时间复杂度：平均O(n㏒₂n)，最小O(n㏒₂n)，最差O(n㏒₂n)；空间复杂度：O(1)
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
*/
type data[T any] struct {
	s    []T
	less func(T, T) bool
}

func (x *data[T]) Len() int {
	return len(x.s)
}

func (x *data[T]) Less(i, j int) bool {
	return x.less(x.s[i], x.s[j])
}

// Swap swaps the elements with indexes i and j.
func (x *data[T]) Swap(i, j int) {
	x.s[i], x.s[j] = x.s[j], x.s[i]
}

func (x *data[T]) Push(v any) {
	if vv, ok := v.(T); ok {
		x.s = append(x.s, vv)
	}

}

// remove and return element Len() - 1.
func (x *data[T]) Pop() any {
	i := x.Len() - 1
	r := x.s[i]
	x.s = x.s[:i]
	return r
}

type Heap[T any] struct {
	d *data[T]
}

func NewHeap[T any](less func(T, T) bool) *Heap[T] {
	return &Heap[T]{d: &data[T]{less: less}}
}

func NewHeapData[T any](d []T, less func(T, T) bool) *Heap[T] {
	r := &data[T]{s: d, less: less}
	heap.Init(r)
	return &Heap[T]{d: r}
}

func (h *Heap[T]) Len() int {
	return h.d.Len()
}

func (h *Heap[T]) Push(v T) {
	heap.Push(h.d, v)
}

func (h *Heap[T]) Top() T {
	if h.Len() > 0 {
		return h.d.s[0]
	}
	var r T
	return r
}
func (h *Heap[T]) Pop() T {
	var r T
	if h.Len() <= 0 {
		return r
	}
	r = h.d.s[0]
	heap.Pop(h.d)
	return r
}

func (h *Heap[T]) Sort() {
	sort.Sort(h.d)
}

func (h *Heap[T]) Remove(i int) T {
	if i < h.Len() {
		return heap.Remove(h.d, i).(T)
	}
	var r T
	return r
}

func (h *Heap[T]) Fix(i int, v T) {
	if i < h.Len() {
		h.d.s[i] = v
		heap.Fix(h.d, i)
	}
}
